数据结构学习笔记

  之前一直谈的是一对一的线性结构，但是还有很多一对多的情况需要处理，所以需要研究这种一对多的数据结构——“树”。

树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。在意一颗非空树中： (1)有且仅有一个特定的称为根(Root)的结点 (2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、…、Tm，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)

  树的定义其实就是我们在讲解栈提到的递归的方法。也就是说树的定义之中还用到了树的概念。这是一种比较新的定义方法。对于树的定义还需要强调两点：

  树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree)。度为0的结点称为叶结点(Leaf)或终点结点；度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。树的度是树内各节点的度的最大值。如图6.2所示，因为这棵树结点的度的最大值是结点D的度，为2，所以树的度也是3。

  结点的子树的根称为该结点的孩子(Child)，相应地，该结点称为孩子的双亲(Parent)。同一个双亲的孩子之间乎称兄弟(Sibling)。结点的祖先是从根到该结点锁经分支上的所有结点。所以对于H来说，D、B、A都是它的祖先。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。

  结点的层次(Level)从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第I层，则其子树的根就在I+1层。其双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度(Depth)或高度。   如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树的有序树，否则称为无序树。   森林(Forest)是m(m>=0)棵互不相交的树的集合。

  在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。

  其中data是数据域，存储结点的数据信息。而parent是指针域，存储该结点的双亲在数组中的下标。以下是我们的双亲表示法的结点结构定义代码。

  有了这样的结构定义，就可以实现双亲表示法了。由于根结点是没有双亲的，所以我们约定根结点的位置域设置为-1，这也就意味着，所有的结点都有它双亲的位置，如图6.4中的树结构和图6.5中的树双亲表示所示。

  这样的存储结构，便可以根据结点的parent指针很容易找到它的双亲结点，所用的时间复杂度为O(1)，直到parent为-1时，表示找到了树结点的根。如果要知道结点的孩子是什么便需要整个结构才行，在次基础上改进一下。   增加一个结点最左边孩子的域，不妨叫它长子域，这样就可以很容易得到结点的孩子。如果没有孩子的结点，这个长子域就设置为-1，如图6.6所示：

  对于有0个或1个孩子结点来说，这样的结构是解决了要找结点孩子的问题。甚至是有2个孩子，知道了长子是谁，另一个当然就是次子了。   另外一个问题场景，关注各兄弟之间的关系，双亲表示便无法体现这样的关系，可以增加一个右兄弟域体现兄弟关系，也就是说，每一个结点如果它存在右兄弟，则记录下右兄弟的下标。同样，如果右兄弟不存在，则赋值为-1.   存储结构的设计是一个非常灵活的过程。一个存储结构设计是否合理，取决于基于该存储结构的运算是否适合、是否方便，时间复杂度好不好等。

  换一种完全不同的考虑方法。由于树中每个结点可能有多棵子树，可以考虑多重链表，即每个结点有多个指针域，其中每个指针指向一颗子树的根结点，我们把这种叫做多重链表表示法。不过，树的每个结点的度，也就是它的孩子个数是不同的。所以可以设计两种方案来解决。

  上述方案中为了要遍历整棵树，把每个结点放到放到一个顺序存储结构的数组中是合理的，但每个结点的孩子有多少是不确定的，所以再对每个结点的孩子建立一个单链表体现它们的关系。   把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。如图6.7所示：

  以下即使孩子表示法的结构定义代码：

  刚才分别才能够双亲的角度和从孩子的角度研究树的存储结构，如果从树结点的兄弟的角度来说，对于树这样的层级结构来说，只研究结点的兄弟是不行的。观察后发现，任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。   其中data是数据域，firstchild为指针域，存储该结点的第一个孩子的结点的存储地址，rightsib是指针域，存储该结点的右兄弟结点的存储地址。

  这种表示法，给查找某个结点的某个孩子带来了方便，只需要通过firstchild找到此结点的长子，然后再通过长子结点的rightsib找到它的二弟，接着一直下去，直到找到具体的孩子。当然，如果想找某个结点的双亲，这个表示法也是有缺陷的，完全可以再增加一个parent指针域来解决快速查找双亲的问题。

  二叉树具有五种基本形式：

  性质1：深度为k的二叉树至多有2k-1个结点(i>=1)。   注意这里一定要看清楚，是2k后再减去1.深度为k意思就是有ke层的二叉树，如果有一层，至多有1 = 21 -1个结点;如果有二层，至多有3 = 22 -1个结点；如果有三层，至多有7 = 23 -1个结点…

  性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1   终端结点数其实就是叶子结点数，而一棵二叉树，除了叶子结点外，剩下的就是度为1或2的结点数，设n1为度是1的结点数。则树T结点总数n=n0+n1+n2   比如图6.10的例子，结点总数为10，它是由A、B、C、D等度为2结点，F、G、H、I、J等度为0的叶子结点和E这个度为1的结点组成。总和为4+1+5=10

  再数一数它的连接线数，由于根结点只有分支出去，没有分支进入，所以分支线总数为结点总数减去1，图6.10就是9个分支。对于A、B、C、D结点来说，它们都有两个分支线出去，而E结点只有一个分支线出去。所以总分支线为4X2+1X1=9。   用代数表达式就是分支线总数=n-1=n1+2n2.因为等式n=n0+n1+n2，所以可以推导出n0+n1+n2-1=n1+2Xn2。结论就是n0 = n2 + 1。

  性质4：具有n个结点的完全二叉树的深度为 [ log ⁡ 2 n \log_2^{n} log2n​] + 1([x]表示不大于x的最大整数)。   由满二叉树的定义可以知道，深度为k的满二叉树的结点数n一定是2k-1。因为这是最多的结点个数。那么对于n=2k-1倒推得到满二叉树的度数为k= log ⁡ 2 n + 1 \log_2^{n+1} log2n+1​，比如结点数为15的满二叉树，度为4。   完全二叉树前面已经提到，它是一棵具有n个结点的二叉树，若按层序编号后其编号与同样深度的满二叉树中编号结点在二叉树中位置相同，那么它就是完全二叉树。也是就说，它的叶子结点只会出现最下面的两层。   它的结点数一定少于等于同样度数的满二叉树的结点数2k-1，但一定多于2k-1-1.即满足2k-1-1 < n data); /*显示结点数据，可以更改为其他对结点操作*/ PreOrderTraverse(T->lchild); /*再先序遍历左子树*/ PreOrderTraverse(T->rchild); /*最后先序遍历右子树*/ } 6.7.4 中序遍历算法 /*二叉树的中序遍历递归算法*/ void InOrderTraverse(BiTree T) { if(T == NULL) { return; } InOrderTraverse(T->lchild); /*中序遍历左子树*/ printf("%c",T->data); /*显示结点数据，可以更改为其他对结点操作*/ InOrderTraverse(T->rchild);/*最后中序遍历右子树*/ } 6.7.5 后序遍历算法 /*二叉树的后序遍历递归算法*/ void PostOrderTraverse(BiTree T) { if(T==NULL) { return; } PostOrderTraverse(T->lchild);/*先后序遍历左子树*/ PostOrderTraverse(T->rchild);/*再后序遍历右子树*/ printf("%c",T->data); /*显示结点数据，可以更改为其他对结点操作*/ } 6.7.6 推导遍历结果

  已知一棵二叉树的前序遍历序列为ABCDEF、中序遍历序列为CBAEDF，请问这棵二叉树的后序遍历结果是多少？前序是根左右，中序是左根右，后序是左右根。牢记这前中后序的原理，即可。结果为CBEFDA

  建立二叉树，也是利用了递归的原理。只不过在原来应该是打印结点的地方，改成了生成结点、给结点赋值的操作而已。

  上述的指针域并不是都充分的利用了，有很多空指针域的存在。建立在已经遍历过的基础之上，可以很清楚的知道任意一个结点，它的前驱和后继是哪一个。但在二叉链表上，只能知道每个结点指向其左右孩子结点的地址，而不知道某个结点的前驱是谁，后继是谁。可以考虑利用哪些空地址，存放指向结点在某种遍历次序的前序和后继结点的地址。这种指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，响应的二叉树就称为线索二叉树(Threaded Binary Tree)。   请看图6.17，把这棵二叉树进行中序遍历后，将所有的空指针域中的rchild，改为指向它的后继结点。于是我们就可以通过指针知道H的后继是D(图中①)，I的后继是B(图中②)，J的后继是E(图中③)，E的后继是A(图中④)，F的后继是C(图中⑤)，G的后继因为不存在而指向NULL(图中⑥)。此时共有6个空指针域被利用。

  再看图6.18，我们将这棵二叉树的所有空指针域中的lchild，改为指向当前结点的前驱。因此H的前驱是NULL(图中①)，I的前驱是D(图中②)，J的前驱是B(图中③)，F的前驱是A(图中④)，G的前驱是C(图中⑤)。一共5个空指针域被利用，正好和上面的后继加起来是11个。 ![6.18.png](https://img-blog.csdnimg.cn/1c4a0621f6ca43faacf4e0218e1c0b15.png#pic_center

  通过图6.19(空心箭头实线为前驱，虚线黑箭头为后继)，就更容易看出，其实线索二叉树，等于是把一棵二叉树转变成了一个双向链表，这样对插入删除结点、查找某个结点都带来了方便。所以对二叉树以某种次序遍历十七变为线索二叉树的过程称做是线索化

  不过好事总是多磨的，问题并没有彻底解决。我们如何知道某一个结点的lchild是指向它的左孩子还是指向前驱？rchild是指向右孩子还是指向后继？比如E结点的lchild是指向它的左孩子J，而rchild却是指向它的后继A。显然我们在决定lchild是指向左孩子还是前驱，rchild是指向右孩子还是后继上是需要一个区分标志的。因此，我们在每个结点再增设两个标志域ltag和rtag，注意ltag和rtag只是存放0或1数字的布尔型变量，其占用的内存空间要小于像lchild和rchild的指针变量。   ltag为0时指向该结点的左孩子，为1时指向该结点的前驱。rtag为0时指向该结点的右孩子，为1时指向该结点的后继。

  线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继的信息只有遍历该二叉树时才能得到，所以线索化的过程就是在遍历的过程中修改空指针的过程。中序遍历线索化的递归函数代码如下：

  新增的代码，if(!p->lchild)表示如果某结点的左指针域为空，因为其前驱结点刚刚访问过，赋值给了pre，所以可将pre赋值给p->lchild，并修改p->LTag=Thrad(也就是定义为1)以完成前驱结点的线索化。   后继就要稍稍麻烦一些，因为此时p结点的后继还没有访问到，因此只能对它的前驱结点pre的右指针rchild做判断，if(!pre->lchild)表示如果为空，则p就是pre的后继，于是pre->rchild=p，并且设置pre->RTag=Thread，完成后继结点的线索化。   完成前驱和后继的判断后，别忘记将当前的结点p赋值给pre，以便于下一次使用。有了线索二叉树后，我们对它进行遍历时发现，其实就等于是操作一个双向链表结构。   和双向链表结构一样，在二叉树线索链表上添加一个头结点，如图6.20所示，并令其lchild域的指针指向二叉树的根结点(图中的①)，其rchild域的指针指向中序遍历时访问的最后一个结点(图中的②)。反之。令二叉树的中序序列中的第一个结点中，lchild域指针和最后一个结点的rchild域指针均指向头结点(图中的③和④)。这样定义的好处就是我们既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。

  遍历的代码如下：

  所以在实际问题中，如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构是非常不错的选择。

  将树转换为二叉树的步骤如下

  如图6.21所示，一棵树经过三个步骤转换为一棵二叉树，初学者容易犯的错误就是在层次调整时，弄错了左右孩子的关系。比如图中F、G本都是树结点B的孩子，是结点E的兄弟，因此转换后，F就是二叉树结点E的右孩子，G是二叉树结点F的右孩子。

  森林是由若干棵树组成，所以完全可以理解为，森林中的每一棵树都是兄弟，可以按照兄弟的处理方法操作。步骤如下：

  二叉树转换为树是树转换为二叉树的逆过程，也就是反过来做而已。如图6.23所示。步骤如下：

  判断一棵二叉树能够转换成一棵树还是森林，标准很简单，那就是只要看这棵二叉树的根结点有没有右孩子，有就是森林，没有就是一棵树。那么如果是转换成森林，步骤如下：

  树的遍历分为两种方式。

  森林的遍历也分为两种方式：

  可如果我们对图6.23的左侧二叉树进行分析就会发现，森林的前序遍历和二叉树的前序遍历结果相同，森林的后序遍历和二叉树的中序遍历结果相同。   这也就告诉我们，当以二叉链表作树的存储结构时，树的先根遍历和后根遍历完全可以借用二叉树的前序遍历和中序遍历的算法来实现。这其实也就证实，我们找到了对树和森林这种复杂问题的简单解决方法。

  在介绍赫夫曼编码前，我们必须得介绍赫夫曼树，而介绍赫夫曼树，我们不得不提这样一个人，美国数学家赫夫曼(David Huffman)，也有的翻译为哈夫曼。他在1952年发明了赫夫曼编码。也就是说，我们介绍的知识全都来自于近60年前这位伟大科学家的研究成果，而我们平时所用的压缩和解压缩技术也都是基于赫夫曼的研究之上发展而来，我们应该要记住他。   什么叫做赫夫曼树呢？我们先来看一个例子。   过去我们小学、中学一般考试都是用百分制来表示学科成绩的。这带来了一个弊端，就是很容易让学生、家长，甚至老师自己都以分取人，让分数代表了一切。有时想想也对，90分和95分也许就只是一道题目对错的差距，但却让两个孩子可能受到完全不同的待遇，这并不公平。于是在如今提倡素质教育的背景下，我们很富哦的学科，特别是小学的学科成绩都改作了优秀、良好、中等、及格和不及格这样模糊的词语，不再通报具体的分数。   不过对于老师来讲，他在对试卷评分的时候，显然不能凭感觉给优良或及格不及格等成绩，因此一般都还是按照百分制算出每个学生的成绩后，再根据统一的标准换算得出五级分制的成绩。比如下面的代码：

  粗略看没什么问题，可是通常都认为，一张好的试卷应该是让学生成绩大部分处于中等或良好的范围，优秀和不及格都应该较少才对。而上面这样的程序，就使得所有的成绩都需要先判断是否几个，再逐级而上得到结果。输入量很大的时候，其实算法是有效率问题的。   有没有好一些的办法，将这棵二叉树重新进行分配，改成如图6.25所示:

  从图中感觉，应该效率要高一些了，到底高多少呢？这样的二叉树又是如何设计出来的呢？我们来看看赫夫曼大叔是如何说的吧。

  我们先把这棵二叉树简化成叶子结点带权的二叉树，如图6.26所示.其中A表示不及格、B表示及格、C表示中等、D表示良好、E表示优秀。每个叶子的分支线上的数字就是刚才我们提到的五级分制的成绩所占比例数。

  赫夫曼大叔说，从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称做路径长度。图6.26的二叉树a中，根结点到结点D的路径长度为4，二叉树b中的根结点到结点D的路径长度为2。树的路径长度就是从树根到每一结点的路径长度之和。二叉树a的树路径长度就为1+1+2+2+3+3+4+4=20。二叉树的树路径长度就为1+2+3+3+2+1+2+2=16。   如果考虑到带权的结点，结点的带权的路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和。假设有n个权值(w1,w2,…wn)，构造一棵有n个叶子结点的二叉树，每个叶子结点戴权wk,每个叶子的路径长为lk，我们通常记作，则其中带权路径长度WPL最小的二叉树称做赫夫曼树。也有不少书中也被称为最优二叉树。   有了赫夫曼对带权路径长度，我们来计算一下图6.26这两棵树的WPL值。二叉树a的WPL=5x1+15x2+40x3+30x4+10x4=315(注意：这里5是A结点的权，1是A结点的路径长度);二叉树b的WPL=5x3+15x3+40x2+30x2+10x2=220   这样的结果意味着什么呢？如果我们现在有10000个学生的百分制成绩需要计算五级分制成绩，用二叉树a的判断方法，需要做31500次比较，而叉树b的判断方法，只需要22000次比较，差不多少了三分之一量，在性能提高不是一点点。   那么现在的问题就是，图6.26的二叉树b这样的树是如何构造出来，这样的二叉树是不是就是最优的赫夫曼树呢？

  通过刚才的步骤，我们可以得出构造赫夫曼树的赫夫曼算法描述。

  当然，赫夫曼研究这种最优树的目的不是为了我们可以转化一下成绩。他的更大目的是为了解决当年远距离通信(主要是电阻)的数据传输的最优化问题。   比如我们有一段文字内容为“BADCADFEED”要网络传输给别人，显然是用二进制的数字（0和1）来表示是很自然的想法。我们现在这段文字只有六个字母ABCDEF，那么我们可以用相应的二进制数据表示，如图6.27所示：

  这样真正传输的数据编码后的“001000011010000011101100100011”，对方接收时可以按照3位一分来译码。如果一篇文章很长，这样的二进制串也就非常可怕。而且事实上，不管是英文、中文或是其他语言，字母或汉字的出现频率是不相同的，比如英语中的几个元音字母“aeiou”，中文中的“的了有在”等汉字都是频率极高。   假设六个字母的频率为A27，B8，C15，D15，E30，F5，合起来正好是100%。那就意味着，我们完全重新按照赫夫曼树来规划它们。   图6.28左图为构造赫夫曼树的过程的权值显示。右图为将权值左分支改为0，右分支改为1后的赫夫曼树。

  此时，我们对这六个字母用其从树根到叶子所经过路径的0或1来编码，可以得到如图6.29所示这样的定义。

  我们将文字内容为“BADCADFEED”再次编码，对比可以看到结果串变小了

  也就是说，我们的数据被压缩了，节约了大约17%的存储或传输成本。随着字符的增加和多字符权重的不同，这种压缩会更加显出其优势。当我们接收到1001010010101001000111100这样压缩过的新编码时，我们应该如何把它解码出来呢？   编码中非0即1，长短不等的话其实是很容易混淆的，所以若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称做前缀编码。你仔细观察就会发现，图6.29所示中的编码就不存在容易与1001、1000混淆的“10”和“100”编码。可仅仅是这样不足以让我们去方便地解码，因此在解码时，还是要用到赫夫曼树，即发送方和接收方必须要约定好同样的赫夫曼编码规则。   当我们接收1001010010101001000111100时，由约定好的赫夫曼树可知，1001得到第一个字母是B，接下来01意味着第二个字符是A。   一般地，设需要编码的字符集为{d1,d2…,dn}，各个字符在电文中出现的次数或频率集合为{w1,w2…,wn},以d1,d2,…,dn作为叶子结点，以w1,w2,…,wn作为相应叶子结点的权值来构造一棵赫夫曼树。规定赫夫曼树的左分支代表为0，右分支代表1，则从根结点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，这就是赫夫曼编码。

  开头我们提到了树的定义，讲到了递归在树定义中的应用。提到了如子树、结点、度、叶子、分支结点、双亲、孩子、层次、深度、森林等诸多概念，这些都是需要在理解的基础上去记忆的。   我们谈到了树的存储结构时，讲了双亲表示法、孩子表示法、孩子兄弟表示法等不同的存储结构。并由孩子兄弟表示法引出了最重要一棵树，二叉树。   二叉树每个结点最多两棵子树，有左右之分。提到了斜树，满二叉树、完全二叉树等特殊二叉树的概念。   我们在人生的道路上就如这二叉树，根节点是我们出生，有的人20岁就选到了最优，有的人30岁还在徘徊，你我终究在做选择。